def fib1(n):
    if n<2:
        return n
    return fib1(n-1) + fib1(n-2)

# 动态规划解法
def fib2(n):
    dp  = [0,1]
    for i in range(2,n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]
n=2
print(fib1(n))
print(fib2(n))